package com.algrithom.tree.dictree;

/**
 * 前缀树
 * 
 * @author think
 * @since 2020/5/26
 * @version 1.0.0
 */
public class TrieTree {
    
    private final TrieNodeSelf root;
    
    public TrieTree(){
        root = new TrieNodeSelf();
    }
    
    public void insert(String word){
        TrieNodeSelf node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar,new TrieNodeSelf());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }
    
    private TrieNodeSelf searchPrefix(String word){
        TrieNodeSelf node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }
    
    public boolean search(String word){
        TrieNodeSelf node = searchPrefix(word);
        return node != null && node.isEnd();
    }
}

class TrieNodeSelf {
    
    private static final int TWENTY_SIX = 26;
    
    private final TrieNodeSelf[] links;
    
    private boolean isEnd;
    
    public TrieNodeSelf(){
        links = new TrieNodeSelf[TWENTY_SIX];
    }
    
    public boolean containsKey(char ch){
        return links[ch - 'a'] != null;
    }
    
    public TrieNodeSelf get(char ch){
        return links[ch - 'a'];
    }
    
    public void put(char ch,TrieNodeSelf node){
        links[ch - 'a'] = node;
    }
    
    public void setEnd(){
        isEnd = true;
    }
    
    public boolean isEnd(){
        return isEnd;
    }
}
